/*
 * @lc app=leetcode.cn id=617 lang=cpp
 *
 * [617] 合并二叉树
 *
 * https://leetcode-cn.com/problems/merge-two-binary-trees/description/
 *
 * algorithms
 * Easy (78.90%)
 * Likes:    947
 * Dislikes: 0
 * Total Accepted:    270.6K
 * Total Submissions: 343K
 * Testcase Example:  '[1,3,2,5]\n[2,1,3,null,4,null,7]'
 *
 * 给你两棵二叉树： root1 和 root2 。
 * 
 * 
 * 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为
 * null 的节点将直接作为新二叉树的节点。
 * 
 * 返回合并后的二叉树。
 * 
 * 注意: 合并过程必须从两个树的根节点开始。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
 * 输出：[3,4,5,5,4,null,7]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：root1 = [1], root2 = [1,2]
 * 输出：[2,2]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 两棵树中的节点数目在范围 [0, 2000] 内
 * -10^4 <= Node.val <= 10^4
 * 
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {

        //前序遍历
        // if(!root1) return root2;
        // if(!root2) return root1;

        // TreeNode* root = new TreeNode(0);

        // root->val = root1->val + root2->val;

        // root->left = mergeTrees(root1->left, root2->left);
        // root->right = mergeTrees(root1->right, root2->right);

        // return root;

        //层序遍历
        if(!root1) return root2;
        if(!root2) return root1;

        queue<TreeNode*> que;
        que.push(root1);
        que.push(root2);

        // TreeNode* root = new TreeNode();

        while(!que.empty()) {
            // int size = que.size();
            // for(int i = 0; i < size; i++) {
                TreeNode* t1 = que.front();
                que.pop();
                TreeNode* t2 = que.front();
                que.pop();

                t1->val += t2->val;

                if(t1->left && t2->left) {
                    que.push(t1->left);
                    que.push(t2->left);
                }

                if(t1->right && t2->right) {
                    que.push(t1->right);
                    que.push(t2->right);
                }

                if(!t1->
                 && t2->left) {
                    t1->left = t2->left;
                }

                if(!t1->right && t2->right) {
                    t1->right = t2->right;
                }

            // }
        }
        return root1;

    }
};
// @lc code=end

